package leetcode_1100;

import java.util.PriorityQueue;

/**
 *@author 周杨 
 *CarPooling_1094 给一个数组二维 里面有人数 在i上车 j下车 问所有人都能完成行程
 *describe:常规题目 变成有限队列 队列里装排序事件 每次比较事件是否超出预期
 *2019年7月23日 下午17:23 
 */
public class CarPooling_1094 {
	public static void main(String[] args) {
		CarPooling_1094 test = new CarPooling_1094();
		int [][] arr = new int[][] {{2,1,5},{3,3,7}};
		System.out.println(test.carPooling(arr, 4));
		System.out.println(test.carPooling(arr, 5));
	}
	
	class Event implements Comparable<Event>{
		int num;
		int time;
		public Event(int num,int time) {
			this.num = num;
			this.time = time;
		}
		//自定义比较器 如果同一时刻有上车和下车的 先下车
		@Override
		public int compareTo(Event o) {
			if(this.time == o.time) return this.num - o.num;
			return this.time - o.time;
		}
	}
	
	
	public boolean carPooling(int[][] trips, int capacity) {
        if(trips.length == 0) return true;
        PriorityQueue<Event> heap = new PriorityQueue<Event>();
        for(int[] trip:trips) {
        	heap.offer(new Event(trip[0],trip[1]));//上车事件
        	heap.offer(new Event(-trip[0],trip[2]));//下车事件
        }
        while(!heap.isEmpty()) {
        	Event event = heap.poll();
        	capacity -= event.num;
        	if(capacity < 0) return false;
        }
        return true;
    }
}
